package Aleehot100;

/**
 * ClassName: c013
 * Package: Aleehot100
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/5/24 17:32
 * @Version 1.0
 * @Since 1.0
 */
public class c013_和为K子数组 {
    public static void main(String[] args) {
         int[] arr = {-2,1,-3,4,-1,2,1,-5,4};
        //int[] arr = {1};
        // int[] arr = {5,4,-1,7,8};
        System.out.println(maxSubArray(arr));
        System.out.println(maxSubArray2(arr));
    }

    public static int maxSubArray(int[] nums) {
        // 前缀和
        int[] sumArr = new int[nums.length];
        int sum = 0;
        // 求最小值
        int[] minArr = new int[nums.length + 1];
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < sumArr.length; i++) {
            sum += nums[i];
            sumArr[i] = sum;
            min = Math.min(sumArr[i], min);
            minArr[i + 1] = min;
        }

        int res = Integer.MIN_VALUE, mid;
        for (int i = 0; i < sumArr.length; i++) {
            if(minArr[i] < 0) {
                mid = sumArr[i] - minArr[i];
            } else {
                mid = sumArr[i];
            }
            if(mid > res) {
                res = mid;
            }
        }
        return res;
    }

    public static int maxSubArray2(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }


}
